#include<vector>
#include<cstdlib>
#include<ctime>
#include<iostream>
using namespace std;
class Solution {
public:
    //用基于快排的原理解决问题，时间复杂度O（N）

    int quicktopk(vector<int>& nums,int left,int right,int k){
        if(left >= right)   return nums[left];
        int l = left-1,r = right+1,i = left;
        int key = getkey(nums,left,right);
        while(i<r){
            if(nums[i] < key)   swap(nums[++l],nums[i++]);
            else if(nums[i] == key) ++i;
            else swap(nums[--r],nums[i]);
        }
        int a = l-left+1,b=r-l-1,c=right-r+1;
        if(c >= k)   return quicktopk(nums,r,right,k);  //在右边区域找
        else if(c+b>= k) return key;    //直接返回key
        else  return quicktopk(nums,left,l,k-b-c);  //在左边区域找
    }
    int getkey(vector<int>& nums,int left,int right){
        int r = rand()%(right-left+1)+left;
        return nums[r];
    }
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return quicktopk(nums,0,nums.size()-1,k);
    }
};

int main(){
    vector<int> v{3,2,1,5,6,4};
    cout<< Solution().findKthLargest(v,2);
    return 0;
}